package com.base.doublepoint.slidingwindows;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LengthOfLongestSubstring {
    /**
     * 3. 无重复字符的最长子串：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     */
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0, ans=0;  //双指针 将[left，right]当作一个窗口
        int n =s.length();
        if (n==0){
            return 0;
        }
        // 需要用集合去避免重复元素
        Set<Character> set=new HashSet<>();

        set.add(s.charAt(left));
        while (right<n-1){  //结束条件，当右侧达到条件

            //先不停增加right，增大窗口
            while (right+1<n&&!set.contains(s.charAt(right+1))){
                set.add(s.charAt(right+1));
                right++;
            }

            //中间提取状态
            ans =Math.max(ans,right-left+1);

            //然后缩小窗口,增大left.
            set.remove(s.charAt(left));
            left++;
        }
        return ans;
    }
    public int lengthOfLongestSubstring1(String s) {
        int res = 0;
        Map<Character, Integer> chars = new HashMap<>();
        for (int i = 0, j = 0; j < s.length(); ++j) {
            char c = s.charAt(j);
            if (chars.containsKey(c)) {
                // chars.get(c)+1 可能比 i 还小，通过 max 函数来锁住左边界
                // e.g. 在"tmmzuxt"这个字符串中，遍历到最后一步时，最后一个字符't'和第一个字符't'是相等的。如果没有 max 函数，i 就会回到第一个't'的索引0处的下一个位置
                i = Math.max(i, chars.get(c) + 1);
            }
            chars.put(c, j);
            res = Math.max(res, j - i + 1);
        }
        return res;
    }



    public static void main(String[] args) {
        String s = "pwwkew";
        LengthOfLongestSubstring longestSubstring = new LengthOfLongestSubstring();
        System.out.println( longestSubstring.lengthOfLongestSubstring(s));

    }

}
